#define  _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#define maxSize 10
//typedef struct SqList {
//	int data[maxSize];
//	int length;
//}SqList;
//
//void displayList(SqList* q) {
//	int i = 0;
//	for (i = 0; i < q->length; i++) {
//		printf("%d ", q->data[i]);
//	}
//	printf("\n");
//}
//
//void nz(SqList*& q) {
//	int left = 0;
//	int right = q->length - 1;
//	int tmp = 0;
//	while (left < right) {
//		tmp = q->data[left];
//		q->data[left] = q->data[right];
//		q->data[right] = tmp;
//		left++;
//		right--; 
//	}
//}
//
//int main()
//{
//	SqList* q = (SqList*)malloc(sizeof(SqList));
//	q->data[0] = 1;
//	q->data[1] = 2;
//	q->data[2] = 3;
//	q->data[3] = 4;
//	q->data[4] = 5;
//	q->length = 5;
//	nz(q);
//	displayList(q);
//
//
//
//
//}

typedef struct LinkList {
	int data;
	struct LinkList* next;
}LinkList;

LinkList* create() {
	LinkList* a = (LinkList*)malloc(sizeof(LinkList));
	LinkList* b = (LinkList*)malloc(sizeof(LinkList));
	LinkList* c = (LinkList*)malloc(sizeof(LinkList));
	LinkList* d = (LinkList*)malloc(sizeof(LinkList));
	LinkList* e = (LinkList*)malloc(sizeof(LinkList));
	a->data = 2;
	b->data = 2;
	c->data = 3;
	d->data = 4;
	e->data = 5;

	a->next = b;
	b->next = c;
	c->next = d;
	d->next = e;
	e->next = NULL;
	LinkList* h = (LinkList*)malloc(sizeof(LinkList));
	h->next = a;
	return h;
}

void yd(LinkList*& L) {
	LinkList* p = L->next;
	LinkList* pre = p;
	while(p != NULL){
		if (p->data < 0) {
			if (L->next == p) {
				p = p->next;
				continue;
			}
			pre->next = p->next;
			p->next = L->next;
			L->next = p;
			p = pre->next;
		}
		else {
			pre = p;
			p = p->next;

		}



	}



}
void fktwo(LinkList*& A, LinkList*& B) {
	B = (LinkList*)malloc(sizeof(LinkList));
	LinkList* rb = B;
	LinkList* ra = A;
	LinkList* p = A->next;

	while (p != NULL) {
		if (p->data % 2 == 1) {
			rb->next = p;
			rb = p;
			ra->next = p->next;
			p = p->next;
		}
		else {
			ra = p;
			p = p->next;
		}
	}
	rb->next = NULL;


}
typedef struct BTNode {
	char data;
	struct BTNode* lchild = NULL;
	struct BTNode* rchild = NULL;
}BTNode;


//void findparent(BTNode* b, char x, BTNode*& p) {
//	if (b != NULL) {
//		if (b->data == x) p = NULL;
//		else if (b->lchild != NULL && b->lchild->data == x)
//			p = b;
//		else if (b->rchild != NULL && b->rchild->data == x)
//			p = b;
//		else
//		{
//			findparent(b->lchild, x, p);
//			if (p == NULL)
//				findparent(b->rchild, x, p);
//		}
//
//	}
//	else {
//		p = NULL;
//	}
//
//}
//int count(BTNode* b, int k, int h) {
//	if (b == NULL)return 0;
//	if (k == h) return count(b->lchild, k, h + 1) + count(b->rchild, k, h + 1) + 1;
//	return count(b->lchild, k, h + 1) + count(b->rchild, k, h + 1);
//}
//
//void countleaf(BTNode* b, int k, int h) {
//	if (b == NULL)return ;
//	if (k == h)
//	{
//		if (b->lchild == NULL && b->rchild == NULL)
//			printf("%c ", b->data);
//	}
//	countleaf(b->lchild, k, h + 1);
//	countleaf(b->rchild, k, h + 1);
//
//
//}



BTNode* createTree() {
	BTNode* a = (BTNode*)malloc(sizeof(BTNode));
	BTNode* b = (BTNode*)malloc(sizeof(BTNode));
	BTNode* c = (BTNode*)malloc(sizeof(BTNode));
	BTNode* d = (BTNode*)malloc(sizeof(BTNode));
	BTNode* e = (BTNode*)malloc(sizeof(BTNode));
	BTNode* f = (BTNode*)malloc(sizeof(BTNode));
	BTNode* g = (BTNode*)malloc(sizeof(BTNode));
	a->lchild = NULL;
	a->rchild = NULL;
	b->lchild = NULL;
	b->rchild = NULL;
	c->lchild = NULL;
	c->rchild = NULL;
	d->lchild = NULL;
	d->rchild = NULL;
	e->lchild = NULL;
	e->rchild = NULL;
	f->lchild = NULL;
	f->rchild = NULL;
	g->lchild = NULL;
	g->rchild = NULL;
	a->data = 'a';
	b->data = 'b';
	c->data = 'c';
	d->data = 'd';
	e->data = 'e';
	f->data = 'f';
	g->data = 'g';

	a->lchild = b;
	a->rchild = c;
	b->lchild = d;
	b->rchild = e;
	c->lchild = f;
	d->lchild = g;

	return a;
}
int count(BTNode* b, int k, int h) {
	if (b == NULL) return 0;
	if (k == 1) return 1;
	if (k == h) return 1;
	return count(b->lchild, k, h + 1) + count(b->rchild, k, h + 1);
}
int countleaf(BTNode* b, int k, int h) {
	if (b == NULL) return 0;
	if (k == h) {
		if (b->lchild == NULL && b->rchild == NULL) {
			return 1;
		}
	}
	return countleaf(b->lchild, k, h + 1) + countleaf(b->rchild, k, h + 1);

}



void display(LinkList* L) {
	LinkList* p = L->next;
	while (p != NULL) {
		printf("%d ", p->data);
		p = p->next;
	}
	printf("\n");
}

int main() {
	BTNode* b = createTree();
	BTNode* p = (BTNode*)malloc(sizeof(BTNode)); ;
	printf("%d ", countleaf(b, 3, 1));



	return 0 ;
}